import java.util.HashMap;
import java.util.Map;

public class a12 {
    public static String minWindow(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int left = 0;
        int right = 0;
        int index = Integer.MAX_VALUE;
        int strStart = 0;
        while (right<s.length()) {
            char c = s.charAt(right);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
            }
            right++;

            while(check(map)){
                if (right - left < index) {
                    index = right - left;
                    strStart = left;
                }

                char c1 = s.charAt(left);
                if (map.containsKey(c1)) {
                    map.put(c1, map.get(c1) + 1);
                }
                left++;
            }
        }
        if (index != Integer.MAX_VALUE)
            return s.substring(strStart, strStart + index);


        return "";
    }
    private static boolean check(Map<Character, Integer> map) {
        for (int value : map.values()) {
            //注意这里的value是可以为负数的，为负数的情况就是，相同的字符右
            // 指针扫描的要比t中的多，比如t是"ABC"，窗口中的字符是"ABBC"
            if (value > 0)
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(minWindow(s, t));
    }
}
